'''
	折半查找（二分查找）
	平均查找长度：ASL = log2(n+1)-1
	条件：1.查找的序列必须是有序列表
		  2.顺序存储结构	
	基本思想：将关键字与有序列表的中间位置的值进行比较，若相等，则查找成功；若不等，则根据关键字与
			 有序列表中间位置的值的比较大小来决定是在前半段和是后半段再次进行比较。
'''

def binary_search(arr, key):
	if arr == None or len(arr) == 0:
		return -1
	low = 0
	high = len(arr) - 1
	while low <= high:
		mild = (low + high) // 2
		if key == arr[mild]:
			return mild
		if key > arr[mild]:
			low = mild + 1
		if key < arr[mild]:
			high = mild - 1
	return 0

arr = [2,4,7,9,10,21,54,76,102]

if __name__ == '__main__':
	res = binary_search(arr, 102)
	print(res)